什麼是雙指針?

雙指針(不是指標)，通常會有是快+慢指針或是左+右指針。

快+慢：快指針移動得比慢指針快，而慢指針會透過快指針去過濾條件。

左+右：兩個指標在同個地方或不同地方的起始位置或移動方向不同。

快+慢指針：

27. Remove Element

Given an integer array nums and an integer val, remove all occurrences of val in nums in-place. The order of the elements may be changed. Then return the number of elements in nums which are not equal to val.

Consider the number of elements in nums which are not equal to val be k, to get accepted, you need to do the following things:

• Change the array nums such that the first k elements of nums contain the elements which are not equal to val. The remaining elements of nums are not important as well as the size of nums.
• Return k.

Custom Judge:

The judge will test your solution with the following code:

int[] nums = [...]; // Input array
int val = ...; // Value to remove
int[] expectedNums = [...]; // The expected answer with correct length.
                            // It is sorted with no values equaling val.

int k = removeElement(nums, val); // Calls your implementation

assert k == expectedNums.length;
sort(nums, 0, k); // Sort the first k elements of nums
for (int i = 0; i < actualLength; i++) {
    assert nums[i] == expectedNums[i];
}

If all assertions pass, then your solution will be accepted.

題目需要你將 val 的數從輸入的陣列中移除，並將剩下的往前挪，然後返回刪除後的陣列的大小：

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int n = nums.size();
        int slow = 0, fast = 0;
        for (; fast < n; ++fast)
        {
            if (nums[fast] != val)
                nums[slow++] = nums[fast];
        }
        return slow;
    }
};

還是不太了解的，畫圖就懂了！

283. Move Zeroes

Given an integer array nums, move all 0's to the end of it while maintaining the relative order of the non-zero elements.

Note that you must do this in-place without making a copy of the array.

Example 1:

Input: nums = [0,1,0,3,12]
Output: [1,3,12,0,0]

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int n = nums.size();
        int slow = 0, fast = 0;
        for (;fast < n; ++fast)
        {
            if (nums[fast] != 0)
                nums[slow++] = nums[fast];
        }
        for (;slow < n; ++slow) // slow以後的都要變成0 (畫圖就懂了)
            nums[slow] = 0;
        
    }
};

左+右指針：

344. Reverse String

Write a function that reverses a string. The input string is given as an array of characters s.

You must do this by modifying the input array in-place with O(1) extra memory.

Example 1:

Input: s = ["h","e","l","l","o"]
Output: ["o","l","l","e","h"]

有時要注意題目給的條件(modifying the input array in-place with O(1) extra memory.)

class Solution {
public:
    void reverseString(vector<char>& s) {
        int left = 0, right = s.size() - 1;
        while (left < right)
            std::swap(s[left++], s[right--]);
    }
};

Note: 雖然很多程式語言都有內建reverse的函數，但是這題的核心就是要我們實現reverse的功能，用內建函數就沒意義了！

(swap不是這題的核心，使用內建或手搓一個都可接受)

392. Is Subsequence

Given two strings s and t, return true if s is a subsequence of t, or false otherwise.

A subsequence of a string is a new string that is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (i.e., "ace" is a subsequence of "abcde" while "aec" is not).

Example 1:

Input: s = "abc", t = "ahbgdc"
Output: true

class Solution {
public:
    bool isSubsequence(string s, string t) {
        int n1 = s.size(), n2 = t.size();
        if (n1 > n2) // 這個判斷不加也可以Accept
            return false;
        int i = 0, j = 0; // i為s的指針、j為t的指針
        for (; j < n2; ++j)
        {
            if (t[j] == s[i]) // 如果改用C的陣列去儲存字元陣列，為什麼這行不會有越界問題?
                i++;
        }
        return i == n1; 
    }
};